package se19team1e.search.props;

/**
 * Java implementation of the Rabin Karp String Search algorithm
 * The algo is O(M+N) - way better than a String contains
 * 
 * @author Arun Manivannan
 * 
 */
public class RabinKarpStringSearchUtil {

	
	/**  Pseudocode
 1 function RabinKarp(string s[1..n], string sub[1..m])
 2     hsub := hash(sub[1..m]);  hs := hash(s[1..m])
 3     for i from 1 to n-m+1
 4         if hs = hsub
 5             if s[i..i+m-1] = sub
 6                 return i
 7         hs := hash(s[i+1..i+m])
 8     return not found
 
	 * @param pattern
	 * @param searchText
	 * @return
	 */
	public static boolean find(String pattern, String searchText) {
		
		System.out.println("Finding "+pattern +" in "+searchText);
		int patternSize = pattern.length(); //Algorithm calls this M
		int patternHash = hash(pattern); //Calculate hash for the pattern

		for (int offset = 0; offset <= searchText.length() - patternSize; offset++) {
			int searchTextHash = hash(searchText.substring(offset, offset + patternSize));
			if (searchTextHash != patternHash){ //Hash isnt equal
				continue; 
			}

			int count = 0; 
			while (count < patternSize && searchText.charAt(offset + count) == pattern.charAt(count))
				count++;

			if (count == patternSize) // yaaay. hash is equal. actual string may or may not be equal
				
				return true; //return exact offset
		}
		return false;
	}
	
	
	/**
	 * Calculates hash for the string.  This is a crippled hash function suggested in the algorithm.
	 * Ideally, I should be calculating by subtracting the left and adding the right. 
	 * And no modulus of a huge prime!!! Considering the usage and the length of the string is generally less than a few hundred chars,
	 * this implementation should be more than optimal. In the worst case, there could be false positives. Big deal. 
	 * 
	 * @param text
	 * @return
	 */
	private static int hash(String text) {
		int hash = 0;
		for (int i = 0; i < text.length(); i++)
			hash = hash + (int) text.charAt(i);
		return hash;
	}
	
}
